package impl.sort;

import anaydis.sort.SorterType;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * Created by IntelliJ IDEA.
 * User: Tomi
 * Date: 04/10/2011
 * Time: 15:22:39
 * To change this template use File | Settings | File Templates.
 */
public class MergeTopDownSorter extends AbstractSorter {
    public MergeTopDownSorter() {
        super(SorterType.MERGE);
    }
    private <T> void merge(Comparator<T> c, List<T> list, int l, int m, int r) {
        if(l<r){
            List<T> aux = new ArrayList<T>();
            for(int i=l; i<=m; i++){
                aux.add(list.get(i));
            }
            for(int j=m+1; j<=r; j++){
                aux.add(list.get(r-j+m+1));
            }
            int i = 0;
            int j = r-l;
            for(int k=l; k<=r; k++){
                if(!greater(c, aux, i, j)){
                    list.set(k, aux.get(i));
                    i++;
                }else{
                    list.set(k, aux.get(j));
                    j--;
                }
            }
        }
    }
    private <T> List<T> createList(List<T> list, int l, int r) {
        List<T> aux = new ArrayList<T>();
        for(int i=l; i<=r; i++){
            aux.add(list.get(i));
        }
        return aux;
    }
    //mergesort top-down
    public <T> void sort(Comparator<T> c, List<T> list) {
        sort(c, list, 0, list.size()-1);
    }
    private <T> void sort(Comparator<T> c, List<T> list, int l, int r) {
        if(l<r){
            int m = l+((r-l)/2);
            sort(c, list, l, m);
            sort(c, list, m+1, r);
            merge(c, list, l, m, r);
        }
    }
}